package stringmatch;

import java.util.LinkedList;
import java.util.List;

public class Kmp {
    /**
     * 朴素字符串匹配算法
     * @param T
     * @param P
     * @return
     */
    int[] nativeStringMatcher(char[] T, char[] P) {
        int n = T.length;
        int m = P.length;
        List<Integer> list = new LinkedList<>();

        for (int i = 0; i <= n-m; i++) {
            int j = 0;
            int tmpi= i;
            while (j < m && T[tmpi] == P[j]) {
                tmpi++;
                j++;
            }
            if (j == m) {
                list.add(i);
                System.out.println("模式已匹配，文本位置：" + i);
            }
        }

        int[] res = new int[list.size()];
        int index = 0;
        for (Integer d: list) {
            res[index++] = d;
        }
        return res;
    }

    /**
     * KMP字符串匹配算法
     * @param s 文本
     * @param m 模式
     * @return m在s中出现的首个位置
     */
    public static int getIndexOf(String s, String m) {
        if (s == null || m == null || s.length() < 1 || m.length() < 1) {
            return -1;
        }

        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();
        int si = 0;
        int mi = 0;
        int[] next = getNextArray(ms);

        while (si < ss.length && mi < ms.length) {
            if (ss[si] == ms[mi]) {
                si++;
                mi++;
            }
            else if (next[mi] == -1) {
                si++;
            }
            else {
                mi = next[mi];
            }
        }

        return (mi == ms.length) ? si -mi : -1;
    }

    /**
     * 计算next数组
     * @param ms 模式串
     * @return next数组
     */
    private static int[] getNextArray(char[] ms) {
        if (ms.length == 1) return new int[]{-1};

        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;

        int pos = 2;
        while (pos < next.length) {
            if (ms[cn] == ms[pos-1]) {
                next[pos] = next[pos-1] + 1;
                cn++;
                pos++;
            }
            else if (cn > 0) {
                cn = next[cn];
            }
            else {
                next[pos] = 0;
                pos++;
            }
        }

        return next;
    }
}
